1. Field of the Invention
The invention relates to graphical resizing of images. More specifically, the invention relates to a method and system for backward mapping graphical data several bytes at a time.
2. Related Art
Resizing graphical data is generally well-known in the art. Two commonly used approaches are forward mapping and backward mapping. In a forward map, the algorithm asks: for each source pixel, where does it land in the destination image? Conversely, for a backward map, the question is for each destination pixel, where does it come from in the source image? A forward map requires arbitration between pixels landing in the same destination, while a backward map requires a certain amount of work for each pixel to determine which source image pixel or pixels it came from, and then it is never necessary to revisit that pixel again.
In a backward mapping scheme, once it has been established for each destination pixel, where it comes from in the source or sources, it is necessary to determine for each source pixel contributing to the destination pixel, a co-efficient of contribution of that source pixel. Typically, for cases where there is more than one source pixel contributing, either two or four pixels are deemed to provide the contribution. This corresponds to bi-linear, and bi-cubic filtering, respectively. The calculation of these coefficients is generally well-known in the art and while computationally intensive, it need be done only once for each row and once for each column. The calculated coefficients are then stored in an array to be accessed during subsequent processing. The above-described scheme will allow one to do either pure horizontal or pure vertical resizing. However, in the event that it were desirable to do both vertical and horizontal resizing at the same time, it would, of course, be necessary to choose some square of source pixels and weight them all with appropriate coefficients. This would require a pixel-by-pixel coefficient calculation and manipulation. By choosing the filter coefficients correctly, it is possible to do stretching in a separable way, i.e. first horizontal stretching and then vertical, or vice versa. Such techniques are well-known in the art.
Coefficients are selected by choosing a geometrical point that is the center of the destination pixel and establishing the function that maps points in the source to the destination, thereby generating a scaled translation where the destination is a linear function in x and y. The inverse of the function yields the point in the source from which the data comes. If the selected point is not the center of the source pixel, it is necessary to interpolate the source data to determine the relative distances between various source pixel centers and weight them accordingly. Thus, the filter coefficients are a function of subpixel position of a backward mapped destination point.
In "Resampling Algorithms for Image Resizing and Rotation" Proc. SPIE Digital Image Processing Applications, vol. 1075, pp. 260-269, 1989, Joseph Ward and David R. Lok provide an algorithm for quantizing the subpixel positions down to e.g. 1/32nd or 1/256th of a pixel and provides ready-made tables of filters which apply for a pixel in that area. Each area is known as a bin. Thus, for each bin, a different filter coefficient is established.
It is relatively straight forward to write a program in C or a C variant to read individual source pixels from a source image and resize them individually. However, there is no straightforward way to operate on multiple adjacent pixels of source data. Operating on multiple pixels of adjacent source data is further complicated by the fact that the data may well be stored in unknown formats. For example, graphical data is commonly stored in band interleaved format where, for example, three successive bytes in memory represent red, green, and blue components of a single pixel. This complicates the issue where it is desired to multiply the adjacent pixel in memory by a filter, since for an arbitrary section of image data, it is not clear whether four bytes represent four pixels or 11/3 pixels. By operating on multiple bytes simultaneously, the speed over standard resizing algorithms can be vastly increased. Therefore, it is desirable to develop a method where multiple bytes of data can be operated on simultaneously without regard for their memory format.